#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
using LL = long long;
const int N = 1e5 + 10;

struct Node
{
    int l, r, add1, add2, sum; // add1: *     add2: + 
}node[N * 4];


int n, m, p;
int q[N];

void pushup(int u){
    node[u].sum = ((LL)node[u << 1].sum + node[u << 1 | 1].sum) % p;
}

void pushdown(Node& root,  Node& left, Node& right){
    left.sum = ((LL) left.sum * root.add1 % p + (LL)(left.r - left.l + 1) * root.add2 % p) % p;
    right.sum = ((LL) right.sum * root.add1 % p + (LL)(right.r - right.l + 1) * root.add2 % p) % p;
    left.add1 = (LL) left.add1 * root.add1 % p;
    left.add2 =  ((LL)left.add2 * root.add1 % p + root.add2) % p;
    right.add1 = (LL) right.add1 * root.add1 % p;
    right.add2 = ((LL)right.add2 * root.add1 % p + root.add2) % p;
    root.add1 = 1, root.add2 = 0;
}
void pushdown(int u){
    pushdown(node[u], node[u << 1], node[u << 1 | 1]);
}

void build(int u, int l, int r){
    if(l == r){
        node[u] = {l, r, 1, 0, q[l]};
    }else{
        node[u].l = l, node[u].r = r, node[u].add1 = 1;
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify1(int u, int l, int r, int k){
    if(node[u].l >= l && node[u].r <= r){
        node[u].sum = (LL)node[u].sum * k % p;
        node[u].add1 = (LL)node[u].add1 * k % p;
        node[u].add2 = (LL)node[u].add2 * k % p;
    }else{
        pushdown(u);
        int mid = (node[u].l + node[u].r) >> 1;
        if(l <= mid) modify1(u << 1, l, r, k);
        if(r > mid) modify1(u << 1 | 1, l, r, k);
        pushup(u);
    }
}// * 


void modify2(int u, int l, int r, int k){
    if(node[u].l >= l && node[u].r <= r){
        node[u].sum = ((LL) node[u].sum + (LL)(node[u].r - node[u].l + 1) * k % p) % p;
        node[u].add2 = ((LL) node[u].add2 + k) % p;
    }else{
        pushdown(u);
        int mid = (node[u].l + node[u].r) >> 1;
        if(l <= mid) modify2(u << 1, l, r, k);
        if(r > mid) modify2(u << 1 | 1, l, r, k);
        pushup(u);
    }
}// *


int query(int u, int l, int r){
    if(node[u].l >= l && node[u].r <= r){
        return node[u].sum;
    }else{
        pushdown(u);
        int res = 0;
        int mid = (node[u].l + node[u].r) >> 1;
        if(l <= mid) res = ((LL)res + query(u << 1, l, r)) % p;
        if(r > mid) res = ((LL) res + query(u << 1 | 1, l, r)) % p;
        return res;
    }
}

int main(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);

    scanf("%d%d", &n, &p);

    for(int i = 1; i <= n; i ++) scanf("%d", &q[i]);

    build(1, 1, n);

    scanf("%d", &m);

    int op, l, r, c;
    while(m--){
        scanf("%d", &op);
        if(op == 1){
            scanf("%d%d%d", &l, &r, &c);
            modify1(1, l, r, c);
        }else if(op == 2){
            scanf("%d%d%d", &l, &r, &c);
            modify2(1, l, r, c);
        }else{
            scanf("%d%d", &l, &r);
            int res = query(1, l, r);
            printf("%d\n", res);
        }
    }

    return 0;
}